1. Field of the Invention
The present invention relates to data compression, and more particularly to a method for accessing data in compressed format for input/output operations.
2. Discussion of the Related Art
Memory Expansion Technology or MXT, a trademark of International Business Machines Corporation, is a memory subsystem for compressing main memory content. MXT effectively doubles the physical memory available to a processor, input/output (I/O) devices and application software. MXT is transparent to CPUs, I/O devices, device drivers, and application software. Although the memory content is in compressed form whenever possible, when the memory is accessed, the content, e.g., data, is first uncompressed and then served to various components of the system such as the processor and I/O devices. Therefore, the system does not have access to data in the compressed form.
An organization of the MXT system is shown in FIG. 1. The main memory 101 in an MXT system comprises compressed data. A third level (L3) cache with 1 KB line size made of double data rate (DDR) SDRAM 102 can be used for accessing main memory 101. An L3 cache 102 comprises uncompressed cache lines. The L3 cache 102 hides the latency of accessing the compressed main memory 101 as a large percentage of accesses results in L3 cache hits. The compressed memory/L3 cache controller 102 performs the real to physical address translation and the compression/decompression functions. A central processing unit (CPU), e.g., 103, and I/O devices connected to an I/O bridge, e.g., 104, can be connected to the main memory 101 through the L3 cache 102. Therefore, for I/O operations, data can be transferred to and from I/O devices through the L3 cache 102. As a consequence, I/O operations can access data in uncompressed form.
An example of a compression algorithm for MXT is a parallelized variation of the Lempel-Ziv algorithm known as LZ1. The compression scheme stores compressed data blocks to the memory in a variable length format. The unit of storage in compressed memory is a 256 byte sector. Depending on its compressibility, a 1 KB block of memory, corresponding to the size of an L3 line, can occupy zero to four sectors in the compressed memory. Due to this variable length format, the controller needs to translate real addresses on the system bus to physical addresses in the physical memory. Real addresses are conventional addresses seen on the processor's external bus. Physical addresses are used for addressing 256 byte sectors in the compressed memory. The real memory is merely an address space whose small sections reside in the L1/L2/L3 caches for immediate access. Memory content not in the cache reside in the physical memory in compressed form. The memory controller performs real-to-physical address translation by a lookup in a Compression Translation Table (CTT), which can be kept at a reserved location in the physical memory.
Referring to FIG. 2, each real address of a 1 KB block, e.g., 201, maps to one entry in the CTT, e.g., 202. Each CTT entry is 16 bytes long. A CTT entry includes four physical sector addresses, e.g., 203, each capable of pointing to a 256-byte sector in the physical memory, e.g., 204. For example, a 1 KB L3 line, which compresses by a factor of two, will occupy two sectors in the physical memory (512 bytes) and the CTT entry will comprise two addresses, each pointing to a sector (FIG. 2). The remaining two pointers will be invalid.
For blocks that compress to less than 120 bits, for example a block full of zeros, a CTT format called trivial line format exists. In this format, the compressed data can be stored entirely in the CTT entry replacing the four address pointers (FIG. 2). Therefore, a trivial block of 1 KB occupies only 16 bytes in the physical memory resulting in a compression ratio of 64 to 1.
MXT systems are configured to have real address space twice the physical memory size, since measurements show that compression ratio of two is typical for many applications. For example, an MXT system with 1 GB of installed SDRAM will appear as having 2 GB of memory.
However, no system or method is known to exist for managing the CTT such that data is accessible to the CPU and I/O operations in a compressed format. Therefore, a need exists for a method of manipulating data table entries, wherein the compressed data can be directly accessed by I/O operations.